package com.practice.niuke.new_direct_practice.class12;

/**
 * 现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，后n2种为纪念币， 每
 * 种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值?
 */
public class Code03_MoneyWays {

    public static int moneyWays(int[] arbitrary, int[] onlyone, int money) {
        if (money < 0) {
            return 0;
        }
        if ((arbitrary == null || arbitrary.length == 0)
                && (onlyone == null || onlyone.length == 0)) {
            return money == 0 ? 1 : 0;
        }

        // 任意张 的数组， 一张的数组，不可能都没有

        int[][] dparb = getDpArb(arbitrary, money);
        int[][] dpone = getDpOne(onlyone, money);
        if (dparb == null) { // 任意张的数组没有，一张的数组有
            return dpone[dpone.length - 1][money];
        }
        if (dpone == null) { // 任意张的数组有，一张的数组没有
            return dparb[dparb.length - 1][money];
        }
        int res = 0;
        for (int i = 0; i <= money; i++) {
            // i元，  劵数组搞定
            // money-i元， 币数组搞定
            res += dparb[dparb.length - 1][i]
                    * dpone[dpone.length - 1][money - i];
        }
        return res;
    }

    /**
     * 任意张求法:
     * arr[0...i号]劵 自由选择张数，搞定j元，多少种方法
     *
     * @param arr   劵数组
     * @param money 需要搞定的钱数
     * @return 方法数
     */
    public static int[][] getDpArb(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        // dp[i][j]  arr[0...i号]劵 自由选择张数，搞定j元，多少种方法
        int[][] dp = new int[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            // arr[0...i号]劵自由选择张数，搞定0元，每种劵都使用0张，因此第0列都为1
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= money; j++) {
            // 假设arr[0]==x,那么只使用x这种面值的货币，可以搞定：
            // 0元（一张也不用）、x元（用1张）、2x元（用2张）、3x元（用3张）、...、n*x元（用n张）这些位置，
            // 因此第一行可以搞定这些位置（注意n*x不能超过整个方法需要搞定的总钱数），没和位置的方法数为1
            dp[0][arr[0] * j] = 1;
        }
        // 0行  0列 填完了，
        // 填普遍位置
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                // 斜率优化
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
            }
        }
        return dp;
    }

    /**
     * 每个位置的前最多只能用一张的求法:
     * arr[0...i号]钱 自由选择用还是不用，搞定j元，多少种方法
     *
     * @param arr   钱数组
     * @param money 需要搞定的钱数
     * @return 方法数
     */
    public static int[][] getDpOne(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        // dp[i][j]  arr[0...i号]钱 自由选择用还是不用，搞定j元，多少种方法
        int[][] dp = new int[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
            }
        }
        return dp;
    }

}
